package binary_tree.leetcode.easy;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bruin_du
 * @description 展平二叉搜索树
 * @date 2022/8/15 20:59
 **/
public class OfferII052_IncreasingBST {
    TreeNode pre;
    public TreeNode increasingBST(TreeNode root) {
        //方法一：使用一个虚拟头结点
        method1(root);

        //方法二：使用前序迭代
        return method2(root);
    }

    private TreeNode method1(TreeNode root) {
        TreeNode dummyHead = new TreeNode(0, null, root);
        pre = dummyHead;
        dfs(root);
        return dummyHead.right;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        root.left = null;
        pre = pre.right = root;
        dfs(root.right);
    }

    private TreeNode method2(TreeNode root) {
        TreeNode head = null, node = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (head == null) head = node;
            node.left = null;
            if (!stack.isEmpty()) node.right = stack.peek();
            node = node.right;
        }
        return head;
    }
}
